话说同步赛因为没打爆零了QwQ
这道Day1T1……个人觉得它领着我自学了一波Kruskal重构树，然后再加上出题人恶意卡SPFA，所以导致我不得不学了一波堆优化（对，差不多就是Dijkstra）
然后其实思维难度就并不算太大了（？）首先求出1号节点到其他点的最短路长度，然后把边按海拔从大到小排序后建一棵Kruskal重构树，这样就只需要找到一个节点u的海拔高于水位线，它的子树的叶子节点就都可以乘车相互到达，在这些点中找到到1号点距离最短的那个就行了。
接下来有一个严肃的问题就是如何找到这个u，我们知道Kruskal重构树是满足堆的性质的，越往上的节点海拔越低，也就是说我们可以用倍增解决这个问题。
所以代码就很简单了：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
using namespace std;
const int N=2000000+110;
const int inf=0x7fffffff;
const int MAXN=110;
const double eps=1e-8;
il int read()
{
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(isdigit(ch))
{
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
int T,n,m,cnt,tot,num,q,k,s;
int head[N],dis[N],Head[N],fa[N],H[N],dep[N],ans[N],lg[N];
int father[N][50];
struct edge
{
int fr,to,nxt,weight,height;
};
il bool cmp(edge e1,edge e2)
{
return e1.height>e2.height;
}
struct node
{
int x,d;
};
il bool operator < (node a,node b)
{
return a.d>b.d;
}
edge e[N],E[N];
il void add_edge(int u,int v,int w,int h)
{
e[++cnt]=(edge){u,v,head[u],w,h};
head[u]=cnt;
}
il void Add_edge(int u,int v)
{
E[++tot]=(edge){u,v,Head[u],0,0};
Head[u]=tot;
E[++tot]=(edge){v,u,Head[v],0,0};
Head[v]=tot;
}
il void Dij(int S)
{
for(ri i=1;i<=n;i++)
dis[i]=inf;
priority_queue<node>heap;
dis[S]=0;
heap.push((node){S,dis[S]});
while(!heap.empty())
{
node now=heap.top();
heap.pop();
if(now.d!=dis[now.x])
continue;
int u=now.x;
for(ri i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(dis[u]+e[i].weight<dis[v])
{
dis[v]=dis[u]+e[i].weight;
heap.push((node){v,dis[v]});
}
}
}
}
il int findf(int x)
{
if(x==fa[x])
return fa[x];
return fa[x]=findf(fa[x]);
}
il void Ex_Kruskal()
{
num=n;
for(ri i=1;i<=n;i++)
fa[i]=i,fa[i+n]=i+n;
for(ri i=1;i<=cnt;i++)
{
int f1=findf(e[i].fr);
int f2=findf(e[i].to);
if(f1!=f2)
{
num++;
Add_edge(num,f1);
Add_edge(num,f2);
fa[f1]=num,fa[f2]=num;
H[num]=e[i].height;
}
}
}
il void DFS(int x,int pre)
{
dep[x]=dep[pre]+1;
father[x][0]=pre;
for(ri i=1;(1<<i)<=dep[x];i++)
father[x][i]=father[father[x][i-1]][i-1];
for(ri i=Head[x];i;i=E[i].nxt)
{
int v=E[i].to;
if(v==pre)
continue;
DFS(v,x);
ans[x]=min(ans[x],ans[v]);
}
}
il int query(int x,int p)
{
for(ri i=20;i>=0;i--)
if((1<<i)<=dep[x]&&H[father[x][i]]>p)
x=father[x][i];
return ans[x];
}
int main()
{
T=read();
while(T--)
{
memset(e,0,sizeof(e));
memset(head,0,sizeof(head));
memset(E,0,sizeof(E));
memset(Head,0,sizeof(Head));
n=read(),m=read();
for(ri i=1;i<=m;i++)
{
int u=read(),v=read(),w=read(),h=read();
add_edge(u,v,w,h);
add_edge(v,u,w,h);
}
Dij(1);
sort(e+1,e+1+cnt,cmp);
Ex_Kruskal();
int rt=findf(1);
for(ri i=1;i<=n;i++)
ans[i]=dis[i],ans[i+n]=inf;
DFS(rt,0);
q=read(),k=read(),s=read();
int last_ans=0;
for(ri i=1;i<=q;i++)
{
int v=read(),p=read();
v=(v+k*last_ans-1)%n+1;
p=(p+k*last_ans)%(s+1);
last_ans=query(v,p);
printf("%d\n",last_ans);
}
}
return 0;
}
然而有一个小问题：按照我的错误计算，N开到1e6应该就够了，然而并不是，我开到2e6才能A。